home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / C / LIB / UNIXLIB37B / !UnixLib37 / src / c / alloc < prev    next >
Text File  |  1996-11-09  |  34KB  |  1,262 lines
  1. /****************************************************************************
  2.  *
  3.  * $Source: /unixb/home/unixlib/source/unixlib37/src/c/RCS/alloc,v $
  4.  * $Date: 1996/05/06 09:01:33 $
  5.  * $Revision: 1.2 $
  6.  * $State: Rel $
  7.  * $Author: unixlib $
  8.  *
  9.  * $Log: alloc,v $
  10.  * Revision 1.2  1996/05/06 09:01:33  unixlib
  11.  * Updates to sources made by Nick Burrett, Peter Burwood and Simon Callan.
  12.  * Saved for 3.7a release.
  13.  *
  14.  * Revision 1.1  1996/04/19 21:26:42  simon
  15.  * Initial revision
  16.  *
  17.  ***************************************************************************/
  18.  
  19. static const char rcs_id[] = "$Id: alloc,v 1.2 1996/05/06 09:01:33 unixlib Rel $";
  20.  
  21. /*
  22.    A version of malloc/free/realloc written by Doug Lea and released to the
  23.    public domain.
  24.  
  25.    VERSION 2.5
  26.  
  27.    * History:
  28.    Based loosely on libg++-1.2X malloc. (It retains some of the overall
  29.    structure of old version,  but most details differ.)
  30.    trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
  31.    fixups Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
  32.    * removed potential for odd address access in prev_chunk
  33.    * removed dependency on getpagesize.h
  34.    * misc cosmetics and a bit more internal documentation
  35.    * anticosmetics: mangled names in macros to evade debugger strangeness
  36.    * tested on sparc, hp-700, dec-mips, rs6000
  37.    with gcc & native cc (hp, dec only) allowing
  38.    Detlefs & Zorn comparison study (to appear, SIGPLAN Notices.)
  39.  
  40.    * Overview
  41.  
  42.    This malloc, like any other, is a compromised design.
  43.  
  44.    Chunks of memory are maintained using a `boundary tag' method as
  45.    described in e.g., Knuth or Standish.  The size of the chunk is
  46.    stored both in the front of the chunk and at the end.  This makes
  47.    consolidating fragmented chunks into bigger chunks very fast.  The
  48.    size field also hold a bit representing whether a chunk is free or
  49.    in use.
  50.  
  51.    Malloced chunks have space overhead of 8 bytes: The preceding and
  52.    trailing size fields.  When a chunk is freed, 8 additional bytes are
  53.    needed for free list pointers. Thus, the minimum allocatable size is
  54.    16 bytes.  8 byte alignment is currently hardwired into the design.
  55.    This seems to suffice for all current machines and C compilers.
  56.    Calling memalign will return a chunk that is both 8-byte aligned
  57.    and meets the requested (power of two) alignment.
  58.  
  59.    It is assumed that 32 bits suffice to represent chunk sizes.  The
  60.    maximum size chunk is 2^31 - 8 bytes.  malloc(0) returns a pointer
  61.    to something of the minimum allocatable size.  Requests for negative
  62.    sizes (when size_t is signed) or with the highest bit set (when
  63.    unsigned) will also return a minimum-sized chunk.
  64.  
  65.    Available chunks are kept in doubly linked lists. The lists are
  66.    maintained in an array of bins using a power-of-two method, except
  67.    that instead of 32 bins (one for each 1 << i), there are 128: each
  68.    power of two is split in quarters.  Chunk sizes up to 128 are
  69.    treated specially; they are categorized on 8-byte boundaries.  This
  70.    both better distributes them and allows for special faster
  71.    processing.
  72.  
  73.    The use of very fine bin sizes closely approximates the use of one
  74.    bin per actually used size, without necessitating the overhead of
  75.    locating such bins. It is especially desirable in common
  76.    applications where large numbers of identically-sized blocks are
  77.    malloced/freed in some dynamic manner, and then later are all freed.
  78.    The finer bin sizes make finding blocks fast, with little wasted
  79.    overallocation. The consolidation methods ensure that once the
  80.    collection of blocks is no longer useful, fragments are gathered
  81.    into bigger chunks awaiting new roles.
  82.  
  83.    The bins av[i] serve as heads of the lists. Bins contain a dummy
  84.    header for the chunk lists. Each bin has two lists. The `dirty' list
  85.    holds chunks that have been returned (freed) and not yet either
  86.    re-malloc'ed or consolidated. (A third free-standing list contains
  87.    returned chunks that have not yet been processed at all.) The `clean'
  88.    list holds split-off fragments and consolidated space. All
  89.    procedures maintain the invariant that no clean chunk physically
  90.    borders another clean chunk. Thus, clean chunks never need to be
  91.    scanned during consolidation.
  92.  
  93.    * Algorithms
  94.  
  95.    Malloc:
  96.  
  97.    This is a very heavily disguised first-fit algorithm.
  98.    Most of the heuristics are designed to maximize the likelihood
  99.    that a usable chunk will most often be found very quickly,
  100.    while still minimizing fragmentation and overhead.
  101.  
  102.    The allocation strategy has several phases:
  103.  
  104.    0. Convert the request size into a usable form. This currently
  105.    means to add 8 bytes overhead plus possibly more to obtain
  106.    8-byte alignment. Call this size `nb'.
  107.  
  108.    1. Check if the last returned (free()'d) or preallocated chunk
  109.    is of the exact size nb. If so, use it.  `Exact' means no
  110.    more than MINSIZE (currently 16) bytes larger than nb. This
  111.    cannot be reduced, since a chunk with size < MINSIZE cannot
  112.    be created to hold the remainder.
  113.  
  114.    This check need not fire very often to be effective.  It
  115.    reduces overhead for sequences of requests for the same
  116.    preallocated size to a dead minimum.
  117.  
  118.    2. Look for a dirty chunk of exact size in the bin associated
  119.    with nb.  `Dirty' chunks are those that have never been
  120.    consolidated.  Besides the fact that they, but not clean
  121.    chunks require scanning for consolidation, these chunks are
  122.    of sizes likely to be useful because they have been
  123.    previously requested and then freed by the user program.
  124.  
  125.    Dirty chunks of bad sizes (even if too big) are never used
  126.    without consolidation. Among other things, this maintains the
  127.    invariant that split chunks (see below) are ALWAYS clean.
  128.  
  129.    2a If there are dirty chunks, but none of the right size,
  130.    consolidate them all, as well as any returned chunks
  131.    (i.e., the ones from step 3). This is all a heuristic for
  132.    detecting and dealing with excess fragmentation and
  133.    random traversals through memory that degrade
  134.    performance especially when the user program is running
  135.    out of physical memory.
  136.  
  137.    3. Pull other requests off the returned chunk list, using one if
  138.    it is of exact size, else distributing into the appropriate
  139.    bins.
  140.  
  141.    4. Try to use the last chunk remaindered during a previous
  142.    malloc. (The ptr to this chunk is kept in var last_remainder,
  143.    to make it easy to find and to avoid useless re-binning
  144.    during repeated splits.  The code surrounding it is fairly
  145.    delicate. This chunk must be pulled out and placed in a bin
  146.    prior to any consolidation, to avoid having other pointers
  147.    point into the middle of it, or try to unlink it.) If
  148.    it is usable, proceed to step 9.
  149.  
  150.    5. Scan through clean chunks in the bin, choosing any of size >=
  151.    nb. Split later (step 9) if necessary below.  (Unlike in step
  152.    2, it is good to split here, because it creates a chunk of a
  153.    known-to-be-useful size out of a fragment that happened to be
  154.    close in size.)
  155.  
  156.    6. Scan through the clean lists of all larger bins, selecting
  157.    any chunk at all. (It will surely be big enough since it is
  158.    in a bigger bin.)  The scan goes upward from small bins to
  159.    large.  It would be faster downward, but could lead to excess
  160.    fragmentation. If successful, proceed to step 9.
  161.  
  162.    7. Consolidate chunks in other dirty bins until a large enough
  163.    chunk is created. Break out to step 9 when one is found.
  164.  
  165.    Bins are selected for consolidation in a circular fashion
  166.    spanning across malloc calls. This very crudely approximates
  167.    LRU scanning -- it is an effective enough approximation for
  168.    these purposes.
  169.  
  170.    8. Get space from the system using sbrk.
  171.  
  172.    Memory is gathered from the system (via sbrk) in a way that
  173.    allows chunks obtained across different sbrk calls to be
  174.    consolidated, but does not require contiguous memory. Thus,
  175.    it should be safe to intersperse mallocs with other sbrk
  176.    calls.
  177.  
  178.    9. If the selected chunk is too big, then:
  179.  
  180.    9a If this is the second split request for nb bytes in a row,
  181.    use this chunk to preallocate up to MAX_PREALLOCS
  182.    additional chunks of size nb and place them on the
  183.    returned chunk list.  (Placing them here rather than in
  184.    bins speeds up the most common case where the user
  185.    program requests an uninterrupted series of identically
  186.    sized chunks. If this is not true, the chunks will be
  187.    binned in step 3 next time.)
  188.  
  189.    9b Split off the remainder and place in last_remainder.
  190.    Because of all the above, the remainder is always a
  191.    `clean' chunk.
  192.  
  193.    10.  Return the chunk.
  194.  
  195.  
  196.    Free:
  197.    Deallocation (free) consists only of placing the chunk on a list
  198.    of returned chunks. free(0) has no effect.  Because freed chunks
  199.    may be overwritten with link fields, this malloc will often die
  200.    when freed memory is overwritten by user programs.  This can be
  201.    very effective (albeit in an annoying way) in helping users track
  202.    down dangling pointers.
  203.  
  204.    Realloc:
  205.    Reallocation proceeds in the usual way. If a chunk can be extended,
  206.    it is, else a malloc-copy-free sequence is taken.
  207.  
  208.    Memalign, valloc:
  209.    memalign arequests more than enough space from malloc, finds a spot
  210.    within that chunk that meets the alignment request, and then
  211.    possibly frees the leading and trailing space. Overreliance on
  212.    memalign is a sure way to fragment space.
  213.  
  214.    * Other implementation notes
  215.  
  216.    This malloc is NOT designed to work in multiprocessing applications.
  217.    No semaphores or other concurrency control are provided to ensure
  218.    that multiple malloc or free calls don't run at the same time, which
  219.    could be disasterous. A single semaphore could be used across malloc,
  220.    realloc, and free. It would be hard to obtain finer granularity.
  221.  
  222.    The implementation is in straight, hand-tuned ANSI C.  Among other
  223.    consequences, it uses a lot of macros. These would be nicer as
  224.    inlinable procedures, but using macros allows use with non-inlining
  225.    compilers, and also makes it a bit easier to control when they
  226.    should be expanded out by selectively embedding them in other macros
  227.    and procedures. (According to profile information, it is almost, but
  228.    not quite always best to expand.)
  229.  
  230.  */
  231.  
  232.  
  233.  
  234. /* TUNABLE PARAMETERS */
  235.  
  236. /*
  237.    SBRK_UNIT is a good power of two to call sbrk with It should
  238.    normally be system page size or a multiple thereof.  If sbrk is very
  239.    slow on a system, it pays to increase this.  Otherwise, it should
  240.    not matter too much.
  241.  */
  242.  
  243. #define SBRK_UNIT 8192
  244.  
  245. /*
  246.    MAX_PREALLOCS is the maximum number of chunks to preallocate.  The
  247.    actual number to prealloc depends on the available space in a
  248.    selected victim, so typical numbers will be less than the maximum.
  249.    Because of this, the exact value seems not to matter too much, at
  250.    least within values from around 1 to 100.  Since preallocation is
  251.    heuristic, making it too huge doesn't help though. It may blindly
  252.    create a lot of chunks when it turns out not to need any more, and
  253.    then consolidate them all back again immediatetly. While this is
  254.    pretty fast, it is better to avoid it.
  255.  */
  256.  
  257. #define MAX_PREALLOCS 5
  258.  
  259.  
  260.  
  261.  
  262. /* preliminaries */
  263.  
  264. #include <stddef.h>        /* for size_t */
  265. #include <stdio.h>        /* needed for malloc_stats */
  266. #include <string.h>
  267. #include <stdlib.h>
  268. #include <unistd.h>
  269.  
  270. #ifdef __cplusplus
  271. extern "C"
  272. {
  273. #endif
  274.  
  275. /*
  276.    extern void *sbrk (size_t);
  277.  */
  278.  
  279. /* mechanics for getpagesize; adapted from bsd/gnu getpagesize.h */
  280.  
  281. #if defined(BSD) || defined(DGUX) || defined(sun) || defined(HAVE_GETPAGESIZE)
  282. /*
  283.    extern size_t getpagesize ();
  284.  */
  285.  
  286. #define malloc_getpagesize getpagesize()
  287. #else
  288. #include <sys/param.h>
  289. #ifdef EXEC_PAGESIZE
  290. #define malloc_getpagesize EXEC_PAGESIZE
  291. #else
  292. #ifdef NBPG
  293. #ifndef CLSIZE
  294. #define malloc_getpagesize NBPG
  295. #else
  296. #define malloc_getpagesize (NBPG * CLSIZE)
  297. #endif
  298. #else
  299. #ifdef NBPC
  300. #define malloc_getpagesize NBPC
  301. #else
  302. #define malloc_getpagesize SBRK_UNIT    /* just guess */
  303. #endif
  304. #endif
  305. #endif
  306. #endif
  307.  
  308. #ifdef __cplusplus
  309. };                /* end of extern "C" */
  310. #endif
  311.  
  312.  
  313.  
  314. /*  CHUNKS */
  315.  
  316.  
  317. struct malloc_chunk
  318.   {
  319.     size_t size;        /* Size in bytes, including overhead. */
  320.     /* Or'ed with INUSE if in use. */
  321.  
  322.     struct malloc_chunk *fd;    /* double links -- used only if free. */
  323.     struct malloc_chunk *bk;
  324.  
  325.   };
  326.  
  327. typedef struct malloc_chunk *mchunkptr;
  328.  
  329. /*  sizes, alignments */
  330.  
  331. #define SIZE_SZ              (sizeof(size_t))
  332. #define MALLOC_MIN_OVERHEAD  (SIZE_SZ + SIZE_SZ)
  333. #define MALLOC_ALIGN_MASK    (MALLOC_MIN_OVERHEAD - 1)
  334. #define MINSIZE              (sizeof(struct malloc_chunk) + SIZE_SZ)
  335.  
  336.  
  337. /* pad request bytes into a usable size */
  338.  
  339. #define request2size(req) \
  340.   (((long)(req) <= 0) ?  MINSIZE : \
  341.     (((req) + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) \
  342.       & ~(MALLOC_ALIGN_MASK)))
  343.  
  344.  
  345. /* Check if m has acceptable alignment */
  346.  
  347. #define aligned_OK(m)    (((size_t)((m)) & (MALLOC_ALIGN_MASK)) == 0)
  348.  
  349.  
  350. /* Check if a chunk is immediately usable */
  351.  
  352. #define exact_fit(ptr, req) ((unsigned)((ptr)->size - (req)) < MINSIZE)
  353.  
  354. /* maintaining INUSE via size field */
  355.  
  356. #define INUSE  0x1        /* size field is or'd with INUSE when in use */
  357.                /* INUSE must be exactly 1, so can coexist with size */
  358.  
  359. #define inuse(p)       ((p)->size & INUSE)
  360. #define set_inuse(p)   ((p)->size |= INUSE)
  361. #define clear_inuse(p) ((p)->size &= ~INUSE)
  362.  
  363.  
  364.  
  365. /* Physical chunk operations  */
  366.  
  367. /* Ptr to next physical malloc_chunk. */
  368.  
  369. #define next_chunk(p)\
  370.   ((mchunkptr)( ((char*)(p)) + ((p)->size & ~INUSE) ))
  371.  
  372. /* Ptr to previous physical malloc_chunk */
  373.  
  374. #define prev_chunk(p)\
  375.   ((mchunkptr)( ((char*)(p)) - ( *((size_t*)((char*)(p) - SIZE_SZ)) & ~INUSE)))
  376.  
  377. /* place size at front and back of chunk */
  378.  
  379. #define set_size(P, Sz)                                                          \
  380. {                                                                               \
  381.   size_t Sss = (Sz);                                                          \
  382.   (P)->size = *((size_t*)((char*)(P) + Sss - SIZE_SZ)) = Sss;                  \
  383. }                                                                              \
  384.  
  385.  
  386. /* conversion from malloc headers to user pointers, and back */
  387.  
  388. #define chunk2mem(p)   ((void*)((char*)(p) + SIZE_SZ))
  389. #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - SIZE_SZ))
  390.  
  391.  
  392.  
  393.  
  394. /* BINS */
  395.  
  396. struct malloc_bin
  397.   {
  398.     struct malloc_chunk dhd;    /* dirty list header */
  399.     struct malloc_chunk chd;    /* clean list header */
  400.   };
  401.  
  402. typedef struct malloc_bin *mbinptr;
  403.  
  404.  
  405. /* field-extraction macros */
  406.  
  407. #define clean_head(b)  (&((b)->chd))
  408. #define first_clean(b) ((b)->chd.fd)
  409. #define last_clean(b)  ((b)->chd.bk)
  410.  
  411. #define dirty_head(b)  (&((b)->dhd))
  412. #define first_dirty(b) ((b)->dhd.fd)
  413. #define last_dirty(b)  ((b)->dhd.bk)
  414.  
  415.  
  416.  
  417.  
  418. /* The bins, initialized to have null double linked lists */
  419.  
  420. #define NBINS     128        /* for 32 bit addresses */
  421. #define LASTBIN   (&(av[NBINS-1]))
  422. #define FIRSTBIN  (&(av[2]))    /* 1st 2 bins unused but simplify indexing */
  423.  
  424. /* Bins < MAX_SMALLBIN_OFFSET are special-cased since they are 8 bytes apart */
  425.  
  426. #define MAX_SMALLBIN_OFFSET  18
  427. #define MAX_SMALLBIN_SIZE   144    /* Max size for which small bin rules apply */
  428.  
  429. /* Helper macro to initialize bins */
  430. #define IAV(i)\
  431.   {{ 0, &(av[i].dhd),  &(av[i].dhd) }, { 0, &(av[i].chd),  &(av[i].chd) }}
  432.  
  433. static struct malloc_bin av[NBINS] =
  434. {
  435.   IAV (0), IAV (1), IAV (2), IAV (3), IAV (4),
  436.   IAV (5), IAV (6), IAV (7), IAV (8), IAV (9),
  437.   IAV (10), IAV (11), IAV (12), IAV (13), IAV (14),
  438.   IAV (15), IAV (16), IAV (17), IAV (18), IAV (19),
  439.   IAV (20), IAV (21), IAV (22), IAV (23), IAV (24),
  440.   IAV (25), IAV (26), IAV (27), IAV (28), IAV (29),
  441.   IAV (30), IAV (31), IAV (32), IAV (33), IAV (34),
  442.   IAV (35), IAV (36), IAV (37), IAV (38), IAV (39),
  443.   IAV (40), IAV (41), IAV (42), IAV (43), IAV (44),
  444.   IAV (45), IAV (46), IAV (47), IAV (48), IAV (49),
  445.   IAV (50), IAV (51), IAV (52), IAV (53), IAV (54),
  446.   IAV (55), IAV (56), IAV (57), IAV (58), IAV (59),
  447.   IAV (60), IAV (61), IAV (62), IAV (63), IAV (64),
  448.   IAV (65), IAV (66), IAV (67), IAV (68), IAV (69),
  449.   IAV (70), IAV (71), IAV (72), IAV (73), IAV (74),
  450.   IAV (75), IAV (76), IAV (77), IAV (78), IAV (79),
  451.   IAV (80), IAV (81), IAV (82), IAV (83), IAV (84),
  452.   IAV (85), IAV (86), IAV (87), IAV (88), IAV (89),
  453.   IAV (90), IAV (91), IAV (92), IAV (93), IAV (94),
  454.   IAV (95), IAV (96), IAV (97), IAV (98), IAV (99),
  455.   IAV (100), IAV (101), IAV (102), IAV (103), IAV (104),
  456.   IAV (105), IAV (106), IAV (107), IAV (108), IAV (109),
  457.   IAV (110), IAV (111), IAV (112), IAV (113), IAV (114),
  458.   IAV (115), IAV (116), IAV (117), IAV (118), IAV (119),
  459.   IAV (120), IAV (121), IAV (122), IAV (123), IAV (124),
  460.   IAV (125), IAV (126), IAV (127)
  461. };
  462.  
  463.  
  464.  
  465. /*
  466.    Auxiliary lists
  467.  
  468.    Even though they use bk/fd ptrs, neither of these are doubly linked!
  469.    They are null-terminated since only the first is ever accessed.
  470.    returned_list is just singly linked for speed in free().
  471.    last_remainder currently has length of at most one.
  472.  
  473.  */
  474.  
  475. static mchunkptr returned_list = 0;    /* List of (unbinned) returned chunks */
  476. static mchunkptr last_remainder = 0;    /* last remaindered chunk from malloc */
  477.  
  478.  
  479.  
  480. /*
  481.    Indexing into bins
  482.  
  483.    Funny-looking mechanics:
  484.    For small bins, the index is just size/8.
  485.    For others, first find index corresponding to the power of 2
  486.    closest to size, using a variant of standard base-2 log
  487.    calculation that starts with the first non-small index and
  488.    adjusts the size so that zero corresponds with it. On each
  489.    iteration, the index is incremented across the four quadrants
  490.    per power of two. (This loop runs a max of 27 iterations;
  491.    usually much less.) After the loop, the remainder is quartered
  492.    to find quadrant. The offsets for loop termination and
  493.    quartering allow bins to start, not end at powers.
  494.  */
  495.  
  496.  
  497. #define findbin(Sizefb, Bfb)                                                  \
  498. {                                                                              \
  499.   size_t Sfb = (Sizefb);                                                      \
  500.   if (Sfb < MAX_SMALLBIN_SIZE)                                                  \
  501.     (Bfb) = (av + (Sfb >> 3));                                                  \
  502.   else                                                                          \
  503.   {                                                                              \
  504.     /* Offset wrt small bins */                                                  \
  505.     size_t Ifb = MAX_SMALLBIN_OFFSET;                                          \
  506.     Sfb >>= 3;                                                                  \
  507.     /* find power of 2 */                                                      \
  508.     while (Sfb >= (MINSIZE * 2)) { Ifb += 4; Sfb >>= 1; }                      \
  509.     /* adjust for quadrant */                                                  \
  510.     Ifb += (Sfb - MINSIZE) >> 2;                                              \
  511.     (Bfb) = av + Ifb;                                                          \
  512.   }                                                                              \
  513. }                                                                              \
  514.  
  515.  
  516.  
  517.  
  518. /* Keep track of the maximum actually used clean bin, to make loops faster */
  519. /* (Not worth it to do the same for dirty ones) */
  520.  
  521. static mbinptr maxClean = FIRSTBIN;
  522.  
  523. #define reset_maxClean                                                          \
  524. {                                                                              \
  525.   while (maxClean > FIRSTBIN && clean_head(maxClean)==last_clean(maxClean))      \
  526.     --maxClean;                                                                  \
  527. }                                                                              \
  528.  
  529.  
  530. /* Macros for linking and unlinking chunks */
  531.  
  532. /* take a chunk off a list */
  533.  
  534. #define unlink(Qul)                                                              \
  535. {                                                                              \
  536.   mchunkptr Bul = (Qul)->bk;                                                  \
  537.   mchunkptr Ful = (Qul)->fd;                                                  \
  538.   Ful->bk = Bul;  Bul->fd = Ful;                                              \
  539. }                                                                              \
  540.  
  541.  
  542. /* place a chunk on the dirty list of its bin */
  543.  
  544. #define dirtylink(Qdl)                                                          \
  545. {                                                                              \
  546.   mchunkptr Pdl = (Qdl);                                                      \
  547.   mbinptr   Bndl;                                                               \
  548.   mchunkptr Hdl, Fdl;                                                          \
  549.                                                                               \
  550.   findbin(Pdl->size, Bndl);                                                      \
  551.   Hdl  = dirty_head(Bndl);                                                       \
  552.   Fdl  = Hdl->fd;                                                               \
  553.                                                                               \
  554.   Pdl->bk = Hdl;  Pdl->fd = Fdl;  Fdl->bk = Hdl->fd = Pdl;                      \
  555. }                                                                              \
  556.  
  557.  
  558.  
  559. /* Place a consolidated chunk on a clean list */
  560.  
  561. #define cleanlink(Qcl)                                                          \
  562. {                                                                              \
  563.   mchunkptr Pcl = (Qcl);                                                      \
  564.   mbinptr Bcl;                                                                   \
  565.   mchunkptr Hcl, Fcl;                                                          \
  566.                                                                               \
  567.   findbin(Qcl->size, Bcl);                                                      \
  568.   Hcl  = clean_head(Bcl);                                                       \
  569.   Fcl  = Hcl->fd;                                                               \
  570.   if (Hcl == Fcl && Bcl > maxClean) maxClean = Bcl;                              \
  571.                                                                               \
  572.   Pcl->bk = Hcl;  Pcl->fd = Fcl;  Fcl->bk = Hcl->fd = Pcl;                      \
  573. }                                                                              \
  574.  
  575.  
  576.  
  577. /* consolidate one chunk */
  578.  
  579. #define consolidate(Qc)                                                          \
  580. {                                                                              \
  581.   for (;;)                                                                      \
  582.   {                                                                              \
  583.     mchunkptr Pc = prev_chunk(Qc);                                              \
  584.     if (!inuse(Pc))                                                              \
  585.     {                                                                          \
  586.       unlink(Pc);                                                              \
  587.       set_size(Pc, Pc->size + (Qc)->size);                                      \
  588.       (Qc) = Pc;                                                              \
  589.     }                                                                          \
  590.     else break;                                                                  \
  591.   }                                                                              \
  592.   for (;;)                                                                      \
  593.   {                                                                              \
  594.     mchunkptr Nc = next_chunk(Qc);                                              \
  595.     if (!inuse(Nc))                                                              \
  596.     {                                                                          \
  597.       unlink(Nc);                                                              \
  598.       set_size((Qc), (Qc)->size + Nc->size);                                  \
  599.     }                                                                          \
  600.     else break;                                                                  \
  601.   }                                                                              \
  602. }                                                                              \
  603.  
  604.  
  605.  
  606. /* Place the held remainder in its bin */
  607. /* This MUST be invoked prior to ANY consolidation */
  608.  
  609. #define clear_last_remainder                                                  \
  610. {                                                                              \
  611.   if (last_remainder != 0)                                                      \
  612.   {                                                                              \
  613.     cleanlink(last_remainder);                                                  \
  614.     last_remainder = 0;                                                          \
  615.   }                                                                              \
  616. }                                                                              \
  617.  
  618.  
  619. /* Place a freed chunk on the returned_list */
  620.  
  621. #define return_chunk(Prc)                                                      \
  622. {                                                                              \
  623.   (Prc)->fd = returned_list;                                                  \
  624.   returned_list = (Prc);                                                       \
  625. }                                                                              \
  626.  
  627.  
  628.  
  629. /* Misc utilities */
  630.  
  631. /* A helper for realloc */
  632.  
  633. static void
  634. free_returned_list ()
  635. {
  636.   clear_last_remainder;
  637.   while (returned_list != 0)
  638.     {
  639.       mchunkptr p = returned_list;
  640.       returned_list = p->fd;
  641.       clear_inuse (p);
  642.       dirtylink (p);
  643.     }
  644. }
  645.  
  646. /* Utilities needed below for memalign */
  647. /* Standard greatest common divisor algorithm */
  648.  
  649. static size_t
  650. gcd (size_t a, size_t b)
  651. {
  652.   size_t tmp;
  653.  
  654.   if (b > a)
  655.     {
  656.       tmp = a;
  657.       a = b;
  658.       b = tmp;
  659.     }
  660.   for (;;)
  661.     {
  662.       if (b == 0)
  663.     return a;
  664.       else if (b == 1)
  665.     return b;
  666.       else
  667.     {
  668.       tmp = b;
  669.       b = a % b;
  670.       a = tmp;
  671.     }
  672.     }
  673. }
  674.  
  675. static size_t
  676. lcm (size_t x, size_t y)
  677. {
  678.   return x / gcd (x, y) * y;
  679. }
  680.  
  681.  
  682.  
  683.  
  684.  
  685. /* Dealing with sbrk */
  686. /* This is one step of malloc; broken out for simplicity */
  687.  
  688. static size_t sbrked_mem = 0;    /* Keep track of total mem for malloc_stats */
  689.  
  690. static mchunkptr
  691. malloc_from_sys (size_t nb)
  692. {
  693.  
  694.   /* The end of memory returned from previous sbrk call */
  695.   static size_t *last_sbrk_end = 0;
  696.  
  697.   mchunkptr p;            /* Will hold a usable chunk */
  698.   size_t *ip;            /* to traverse sbrk ptr in size_t units */
  699.  
  700.   /* Find a good size to ask sbrk for.  */
  701.   /* Minimally, we need to pad with enough space */
  702.   /* to place dummy size/use fields to ends if needed */
  703.  
  704.   size_t sbrk_size = ((nb + SBRK_UNIT - 1 + SIZE_SZ + SIZE_SZ)
  705.               / SBRK_UNIT) * SBRK_UNIT;
  706.  
  707.   ip = (size_t *) (sbrk (sbrk_size));
  708.   if ((char *) ip == (char *) (-1))    /* sbrk returns -1 on failure */
  709.     return 0;
  710.  
  711.   sbrked_mem += sbrk_size;
  712.  
  713.   if (last_sbrk_end != &ip[-1])    /* Is this chunk continguous with last? */
  714.     {
  715.       /* It's either first time through or someone else called sbrk. */
  716.       /* Arrange end-markers at front & back */
  717.  
  718.       /* Shouldn't be necessary, but better to be safe */
  719.       while (!aligned_OK (ip))
  720.     {
  721.       ++ip;
  722.       sbrk_size -= SIZE_SZ;
  723.     }
  724.  
  725.       /* Mark the front as in use to prevent merging. (End done below.) */
  726.       /* Note we can get away with only 1 word, not MINSIZE overhead here */
  727.  
  728.       *ip++ = SIZE_SZ | INUSE;
  729.  
  730.       p = (mchunkptr) ip;
  731.       set_size (p, sbrk_size - (SIZE_SZ + SIZE_SZ));
  732.  
  733.     }
  734.   else
  735.     {
  736.       mchunkptr l;
  737.  
  738.       /* We can safely make the header start at end of prev sbrked chunk. */
  739.       /* We will still have space left at the end from a previous call */
  740.       /* to place the end marker, below */
  741.  
  742.       p = (mchunkptr) (last_sbrk_end);
  743.       set_size (p, sbrk_size);
  744.  
  745.       /* Even better, maybe we can merge with last fragment: */
  746.  
  747.       l = prev_chunk (p);
  748.       if (!inuse (l))
  749.     {
  750.       unlink (l);
  751.       set_size (l, p->size + l->size);
  752.       p = l;
  753.     }
  754.  
  755.     }
  756.  
  757.   /* mark the end of sbrked space as in use to prevent merging */
  758.  
  759.   last_sbrk_end = (size_t *) ((char *) p + p->size);
  760.   *last_sbrk_end = SIZE_SZ | INUSE;
  761.  
  762.   return p;
  763. }
  764.  
  765.  
  766.  
  767.  
  768. /* Consolidate dirty chunks until create one big enough for current req. */
  769. /* Call malloc_from_sys if can't create one. */
  770. /* This is just one phase of malloc, but broken out for sanity */
  771.  
  772. static mchunkptr
  773. malloc_find_space (size_t nb)
  774. {
  775.   /* Circularly traverse bins so as not to pick on any one too much */
  776.   static mbinptr rover = LASTBIN;    /* Circular roving ptr */
  777.  
  778.   mbinptr origin = rover;
  779.   mbinptr b = rover;
  780.  
  781.   /* Preliminaries.  */
  782.   clear_last_remainder;
  783.   reset_maxClean;
  784.  
  785.   do
  786.     {
  787.       mchunkptr p;
  788.  
  789.       while ((p = last_dirty (b)) != dirty_head (b))
  790.     {
  791.       unlink (p);
  792.       consolidate (p);
  793.  
  794.       if (p->size >= nb)
  795.         {
  796.           rover = b;
  797.           return p;
  798.         }
  799.       else
  800.         cleanlink (p);
  801.     }
  802.  
  803.       b = (b == FIRSTBIN) ? LASTBIN : b - 1;    /* circularly sweep down */
  804.  
  805.     }
  806.   while (b != origin);
  807.  
  808.   /* If no return above, chain to the next step of malloc */
  809.   return malloc_from_sys (nb);
  810. }
  811.  
  812.  
  813. /* Clear out dirty chunks from a bin, along with the free list. */
  814. /* Invoked from malloc when things look too fragmented */
  815.  
  816. static void
  817. malloc_clean_bin (mbinptr bin)
  818. {
  819.   mchunkptr p;
  820.  
  821.   clear_last_remainder;
  822.  
  823.   while ((p = last_dirty (bin)) != dirty_head (bin))
  824.     {
  825.       unlink (p);
  826.       consolidate (p);
  827.       cleanlink (p);
  828.     }
  829.  
  830.   while (returned_list != 0)
  831.     {
  832.       p = returned_list;
  833.       returned_list = p->fd;
  834.       clear_inuse (p);
  835.       consolidate (p);
  836.       cleanlink (p);
  837.     }
  838. }
  839.  
  840.  
  841.  
  842.  
  843. /*   Finally, the user-level functions  */
  844.  
  845.  
  846. void *
  847. malloc (size_t bytes)
  848. {
  849.   static size_t previous_request = 0;    /* To control preallocation */
  850.  
  851.   size_t nb = request2size (bytes);    /* padded request size */
  852.   mbinptr bin;            /* corresponding bin */
  853.   mchunkptr victim;        /* will hold selected chunk */
  854.  
  855.   /* ----------- Peek at returned_list; hope for luck */
  856.  
  857.   if ((victim = returned_list) != 0 &&
  858.       exact_fit (victim, nb))    /* size check works even though INUSE set */
  859.     {
  860.       returned_list = victim->fd;
  861.       return chunk2mem (victim);
  862.     }
  863.  
  864.   findbin (nb, bin);        /*  Need to know bin for other traversals */
  865.  
  866.   /* ---------- Scan dirty list of own bin */
  867.  
  868.   /* Code for small bins special-cased out since */
  869.   /* no size check or traversal needed and */
  870.   /* clean bins are exact matches so might as well test now */
  871.  
  872.   if (nb < MAX_SMALLBIN_SIZE)
  873.     {
  874.       if (((victim = first_dirty (bin)) != dirty_head (bin)) ||
  875.       ((victim = last_clean (bin)) != clean_head (bin)))
  876.     {
  877.       unlink (victim);
  878.       set_inuse (victim);
  879.       return chunk2mem (victim);
  880.     }
  881.     }
  882.   else
  883.     {
  884.       if ((victim = first_dirty (bin)) != dirty_head (bin))
  885.     {
  886.       do
  887.         {
  888.           if (exact_fit (victim, nb))
  889.         {
  890.           unlink (victim);
  891.           set_inuse (victim);
  892.           return chunk2mem (victim);
  893.         }
  894.           else
  895.         victim = victim->fd;
  896.         }
  897.       while (victim != dirty_head (bin));
  898.  
  899.       /* If there were chunks in there but none matched, then */
  900.       /* consolidate all chunks in this bin plus those on free list */
  901.       /* to prevent further traversals and fragmentation. */
  902.  
  903.       malloc_clean_bin (bin);
  904.     }
  905.     }
  906.  
  907.   /* ------------ Search free list */
  908.  
  909.   if ((victim = returned_list) != 0)
  910.     {
  911.       do
  912.     {
  913.       mchunkptr next = victim->fd;
  914.       if (exact_fit (victim, nb))
  915.         {
  916.           returned_list = next;
  917.           return chunk2mem (victim);
  918.         }
  919.       else
  920.         /* Place unusable chunks in their bins  */
  921.         {
  922.           clear_inuse (victim);
  923.           dirtylink (victim);
  924.           victim = next;
  925.         }
  926.     }
  927.       while (victim != 0);
  928.       returned_list = 0;
  929.     }
  930.  
  931.   /* -------------- Try the remainder from last successful split */
  932.  
  933.   if ((victim = last_remainder) != 0 && victim->size >= nb)
  934.     {
  935.       last_remainder = 0;    /* reset for next time */
  936.       goto split;
  937.     }
  938.  
  939.   /* -------------- Scan through own clean bin */
  940.  
  941.   /* (Traversing back-to-front tends to choose `old' */
  942.   /*  chunks that could not be further consolidated.) */
  943.  
  944.   for (victim = last_clean (bin); victim != clean_head (bin); victim = victim->bk)
  945.     {
  946.       if (victim->size >= nb)
  947.     {
  948.       unlink (victim);
  949.       goto split;
  950.     }
  951.     }
  952.  
  953.   /* -------------- Try all bigger clean bins */
  954.  
  955.   /* (Scanning upwards is slower but prevents fragmenting big */
  956.   /* chunks that we might need later. If there aren't any smaller */
  957.   /* ones, most likely we got a big one from last_remainder anyway.) */
  958.  
  959.   {
  960.     mbinptr b;
  961.  
  962.     for (b = bin + 1; b <= maxClean; ++b)
  963.       {
  964.     if ((victim = last_clean (b)) != clean_head (b))
  965.       {
  966.         unlink (victim);
  967.         goto split;
  968.       }
  969.       }
  970.   }
  971.  
  972.   /* -------------  Consolidate or sbrk */
  973.  
  974.   victim = malloc_find_space (nb);
  975.  
  976.   if (victim == 0)        /* propagate failure */
  977.     return 0;
  978.  
  979.   /* -------------- Possibly split victim chunk */
  980.  
  981. split:
  982.   {
  983.     size_t room = victim->size - nb;
  984.     if (room >= MINSIZE)
  985.       {
  986.     mchunkptr v = victim;    /* Hold so can break up in prealloc */
  987.  
  988.     set_size (victim, nb);    /* Adjust size of chunk to be returned */
  989.  
  990.     /* ---------- Preallocate */
  991.  
  992.     /* Try to preallocate some more of this size if */
  993.     /* last (split) req was of same size */
  994.  
  995.     if (previous_request == nb)
  996.       {
  997.         int i;
  998.  
  999.         for (i = 0; i < MAX_PREALLOCS && room >= nb + MINSIZE; ++i)
  1000.           {
  1001.         room -= nb;
  1002.  
  1003.         v = (mchunkptr) ((char *) (v) + nb);
  1004.         set_size (v, nb);
  1005.         set_inuse (v);    /* free-list chunks must have inuse set */
  1006.         return_chunk (v);    /* add to free list */
  1007.           }
  1008.       }
  1009.  
  1010.     previous_request = nb;    /* record for next time */
  1011.  
  1012.     /* ---------- Create remainder chunk  */
  1013.  
  1014.     /* Get rid of the old one first */
  1015.     if (last_remainder != 0)
  1016.       cleanlink (last_remainder);
  1017.  
  1018.     last_remainder = (mchunkptr) ((char *) (v) + nb);
  1019.     set_size (last_remainder, room);
  1020.       }
  1021.  
  1022.     set_inuse (victim);
  1023.     return chunk2mem (victim);
  1024.   }
  1025. }
  1026.  
  1027.  
  1028.  
  1029.  
  1030. void
  1031. free (void *mem)
  1032. {
  1033.   if (mem != 0)
  1034.     {
  1035.       mchunkptr p = mem2chunk (mem);
  1036.       return_chunk (p);
  1037.     }
  1038. }
  1039.  
  1040.  
  1041.  
  1042.  
  1043. void *
  1044. realloc (void *mem, size_t bytes)
  1045. {
  1046.   if (bytes == 0)
  1047.     {
  1048.       free (mem);
  1049.       return malloc (0);
  1050.     }
  1051.   else if (mem == NULL)
  1052.     return malloc (bytes);
  1053.   else
  1054.     {
  1055.       size_t nb = request2size (bytes);
  1056.       mchunkptr p = mem2chunk (mem);
  1057.       size_t oldsize;
  1058.       long room;
  1059.       mchunkptr nxt;
  1060.  
  1061.       if (p == returned_list)    /* support realloc-last-freed-chunk idiocy */
  1062.     returned_list = returned_list->fd;
  1063.  
  1064.       clear_inuse (p);
  1065.       oldsize = p->size;
  1066.  
  1067.       /* try to expand (even if already big enough), to clean up chunk */
  1068.  
  1069.       free_returned_list ();    /* make freed chunks available to consolidate */
  1070.  
  1071.       while (!inuse (nxt = next_chunk (p)))    /* Expand the chunk forward */
  1072.     {
  1073.       unlink (nxt);
  1074.       set_size (p, p->size + nxt->size);
  1075.     }
  1076.  
  1077.       room = (long) p->size - nb;
  1078.       if (room >= 0)        /* Successful expansion */
  1079.     {
  1080.       if (room >= MINSIZE)    /* give some back if possible */
  1081.         {
  1082.           mchunkptr remainder = (mchunkptr) ((char *) (p) + nb);
  1083.           set_size (remainder, (int) room);
  1084.           cleanlink (remainder);
  1085.           set_size (p, nb);
  1086.         }
  1087.       set_inuse (p);
  1088.       return chunk2mem (p);
  1089.     }
  1090.       else
  1091.     /* Could not expand. Get another chunk and copy. */
  1092.     {
  1093.       void *newmem;
  1094.  
  1095.       set_inuse (p);    /* don't let malloc consolidate us yet! */
  1096.       newmem = malloc (nb);
  1097.       if (newmem == 0)
  1098.         return 0;
  1099.  
  1100.       memmove (newmem, mem, oldsize);
  1101.       free (mem);
  1102.       return newmem;
  1103.     }
  1104.     }
  1105. }
  1106.  
  1107.  
  1108.  
  1109. /* Return a pointer to space with at least the alignment requested */
  1110. /* Alignment argument should be a power of two */
  1111.  
  1112. void *
  1113. memalign (size_t alignment, size_t bytes)
  1114. {
  1115.   mchunkptr p;
  1116.   size_t nb = request2size (bytes);
  1117.   size_t room;
  1118.  
  1119.   /* find an alignment that both we and the user can live with: */
  1120.   /* least common multiple guarantees mutual happiness */
  1121.   size_t align = lcm (alignment, MALLOC_MIN_OVERHEAD);
  1122.  
  1123.   /* call malloc with worst case padding to hit alignment; */
  1124.   /* we will give back extra */
  1125.  
  1126.   size_t req = nb + align + MINSIZE;
  1127.   void *m = malloc (req);
  1128.  
  1129.   if (m == 0)
  1130.     return 0;            /* propagate failure */
  1131.  
  1132.   p = mem2chunk (m);
  1133.   clear_inuse (p);
  1134.  
  1135.  
  1136.   if (((size_t) (m) % align) != 0)    /* misaligned */
  1137.     {
  1138.  
  1139.       /* find an aligned spot inside chunk */
  1140.  
  1141.       mchunkptr ap = (mchunkptr) ((((size_t) (m) + align - 1) & -align) - SIZE_SZ);
  1142.  
  1143.       size_t gap = (size_t) (ap) - (size_t) (p);
  1144.  
  1145.       /* we need to give back leading space in a chunk of at least MINSIZE */
  1146.  
  1147.       if (gap < MINSIZE)
  1148.     {
  1149.       /* This works since align >= MINSIZE */
  1150.       /* and we've malloc'd enough total room */
  1151.  
  1152.       ap = (mchunkptr) ((size_t) (ap) + align);
  1153.       gap += align;
  1154.     }
  1155.  
  1156.       room = p->size - gap;
  1157.  
  1158.       /* give back leader */
  1159.       set_size (p, gap);
  1160.       dirtylink (p);        /* Don't really know if clean or dirty; be safe */
  1161.  
  1162.       /* use the rest */
  1163.       p = ap;
  1164.       set_size (p, room);
  1165.     }
  1166.  
  1167.   /* also give back spare room at the end */
  1168.  
  1169.   room = p->size - nb;
  1170.   if (room >= MINSIZE)
  1171.     {
  1172.       mchunkptr remainder = (mchunkptr) ((char *) (p) + nb);
  1173.       set_size (remainder, room);
  1174.       dirtylink (remainder);    /* Don't really know; be safe */
  1175.       set_size (p, nb);
  1176.     }
  1177.  
  1178.   set_inuse (p);
  1179.   return chunk2mem (p);
  1180.  
  1181. }
  1182.  
  1183.  
  1184.  
  1185. /* Derivatives */
  1186.  
  1187. void *
  1188. valloc (size_t bytes)
  1189. {
  1190.   /* Cache result of getpagesize */
  1191.   static size_t malloc_pagesize = 0;
  1192.  
  1193.   if (malloc_pagesize == 0)
  1194.     malloc_pagesize = malloc_getpagesize;
  1195.   return memalign (malloc_pagesize, bytes);
  1196. }
  1197.  
  1198. void *
  1199. calloc (size_t n, size_t elem_size)
  1200. {
  1201.   size_t sz = n * elem_size;
  1202.   void *p = malloc (sz);
  1203.   if (p != 0)
  1204.     memset (p, 0, sz);
  1205.   return p;
  1206. }
  1207.  
  1208. void
  1209. cfree (void *mem)
  1210. {
  1211.   free (mem);
  1212. }
  1213.  
  1214. size_t
  1215. malloc_usable_size (void *mem)
  1216. {
  1217.   if (mem == 0)
  1218.     return 0;
  1219.   else
  1220.     {
  1221.       mchunkptr p = (mchunkptr) ((char *) (mem) - SIZE_SZ);
  1222.       size_t sz = p->size & ~(INUSE);
  1223.       /* report zero if not in use or detectably corrupt */
  1224.       if (p->size == sz || sz != *((size_t *) ((char *) (p) + sz - SIZE_SZ)))
  1225.     return 0;
  1226.       else
  1227.     return sz - MALLOC_MIN_OVERHEAD;
  1228.     }
  1229. }
  1230.  
  1231.  
  1232. void
  1233. malloc_stats (void)
  1234. {
  1235.  
  1236.   /* Traverse through and count all sizes of all chunks */
  1237.  
  1238.   size_t avail = 0;
  1239.   size_t malloced_mem;
  1240.  
  1241.   mbinptr b;
  1242.  
  1243.   free_returned_list ();
  1244.  
  1245.   for (b = FIRSTBIN; b <= LASTBIN; ++b)
  1246.     {
  1247.       mchunkptr p;
  1248.  
  1249.       for (p = first_dirty (b); p != dirty_head (b); p = p->fd)
  1250.     avail += p->size;
  1251.  
  1252.       for (p = first_clean (b); p != clean_head (b); p = p->fd)
  1253.     avail += p->size;
  1254.     }
  1255.  
  1256.   malloced_mem = sbrked_mem - avail;
  1257.  
  1258.   fprintf (stderr, "total mem = %10u\n", sbrked_mem);
  1259.   fprintf (stderr, "in use    = %10u\n", malloced_mem);
  1260.  
  1261. }
  1262.